package LeetCode.LC64;

/**
 * 64. 最小路径和
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * @author corn
 * @create 2020-07-21-16:51
 */
public class MinPathSum {
    public static void main(String[] args) {
        int[][] grid = {{1,4,1,1},
                        {3,2,2,1},
                        {3,1,1,1}};
        Solution sol = new Solution();
        System.out.println(sol.minPathSum(grid));
    }
}
class Solution {
    //一维数组动态规划：只用一行数据作为数据
    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length];
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j != grid[0].length - 1)
                    //最下面一行:当前格等于当前格数据+右边一格数据
                    dp[j] = grid[i][j] + dp[j + 1];
                else if (j == grid[0].length - 1 && i != grid.length - 1)
                    //最右边一列：当前格等于当前格数据+下边一格数据
                    dp[j] = grid[i][j] + dp[j];
                else if (j != grid[0].length - 1 && i != grid.length - 1)
                    //中间格子：当前格等于当前格数据+min(下边一格数据,右边一格数据)
                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
                else
                    //最后一个格子
                    dp[j] = grid[i][j];
            }
        }
        return dp[0];
    }
//    //二维数组动态规划：不占用多余内存空间
//    public int minPathSum(int[][] grid) {
//        for (int i = grid.length - 1; i >= 0; i--) {
//            for (int j = grid[0].length - 1; j >= 0; j--) {
//                if(i == grid.length - 1 && j != grid[0].length - 1)
//                    //最下面一行:当前格等于当前格数据+右边一格数据
//                    grid[i][j] = grid[i][j] +  grid[i][j + 1];
//                else if(j == grid[0].length - 1 && i != grid.length - 1)
//                    //最右边一列：当前格等于当前格数据+下边一格数据
//                    grid[i][j] = grid[i][j] + grid[i + 1][j];
//                else if(j != grid[0].length - 1 && i != grid.length - 1)
//                    //中间格子：当前格等于当前格数据+min(下边一格数据,右边一格数据)
//                    grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j], grid[i][j + 1]);
//                else
//                    //最后一个格子
//                    grid[i][j] = grid[i][j];
//            }
//        }
//        return grid[0][0];
//    }
//    //二维数组动态规划
//    public int minPathSum(int[][] grid) {
//        int[][] dp = new int[grid.length][grid[0].length];
//        for (int i = grid.length - 1; i >= 0; i--) {
//            for (int j = grid[0].length - 1; j >= 0; j--) {
//                if(i == grid.length - 1 && j != grid[0].length - 1)
//                    //最下面一行:当前格等于当前格数据+右边一格数据
//                    dp[i][j] = grid[i][j] +  dp[i][j + 1];
//                else if(j == grid[0].length - 1 && i != grid.length - 1)
//                    //最右边一列：当前格等于当前格数据+下边一格数据
//                    dp[i][j] = grid[i][j] + dp[i + 1][j];
//                else if(j != grid[0].length - 1 && i != grid.length - 1)
//                    //中间格子：当前格等于当前格数据+min(下边一格数据,右边一格数据)
//                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
//                else
//                    //最后一个格子
//                    dp[i][j] = grid[i][j];
//            }
//        }
//        return dp[0][0];
//    }
//    //方法一：递归（暴力破解）缺点：耗时 时间复杂度：O(2^（m+n）)。
//    public int minPathSum(int[][] grid) {
//        return minPath(grid,0,0);
//    }
//    public int minPath(int[][] grid,int x,int y){
//        if(x == grid.length || y == grid[0].length)
//            return Integer.MAX_VALUE;//由于不是二位数组中的数据，所以返回极大数。
//        if(x == grid.length-1 && y == grid[0].length -1)
//            return grid[x][y];//最后一个数
//        return grid[x][y] + Math.min(minPath(grid,x+1,y),minPath(grid,x,y+1));//放回本身+后续的数据。
//    }
}
